#include "main/utils.h"
using namespace std;

bool canPartitionCore(int i, int j, const vector<int>& arr, vector<vector<int>>& dp) {
  if (dp[i][j] == -1) {
    if (j == 0) {
      dp[i][j] = 1;
    } else if (i == 0) {
      dp[i][j] = 0;
    } else {
      dp[i][j] = canPartitionCore(i - 1, j, arr, dp);
      if (!dp[i][j] && j >= arr[i - 1]) {
        dp[i][j] = canPartitionCore(i - 1, j - arr[i - 1], arr, dp);
      }
    }
  }
  return dp[i][j];
}

bool canPartition1(const vector<int>& arr) {
  int sum = 0;
  for (auto ele : arr) {
    sum += ele;
  }
  if (sum % 2) {
    return false;
  }
  sum /= 2;

  int len = arr.size();
  vector<vector<int>> dp;
  dp.resize(len + 1);
  for (int i = 0; i < len + 1; ++i) {
    dp[i].resize(sum + 1, -1);
  }

  return canPartitionCore(len, sum, arr, dp);
}

bool canPartition2(const vector<int>& arr) {
  int sum = 0;
  for (auto ele : arr) {
    sum += ele;
  }
  if (sum % 2) {
    return false;
  }
  sum /= 2;

  int len = arr.size();
  vector<vector<int>> dp;
  dp.resize(len + 1);
  for (int i = 0; i < len + 1; ++i) {
    dp[i].resize(sum + 1, 0);
  }
  dp[0][0] = 1;
  for (int i = 1; i < len + 1; ++i) {
    dp[i][0] = 1;
    for (int j = 1; j < sum + 1; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (!dp[i][j] && j >= arr[i - 1]) {
        dp[i][j] = dp[i - 1][j - arr[i - 1]];
      }
    }
  }
  return dp[len][sum];
}

bool canPartition3(const vector<int>& arr) {
  int sum = 0;
  for (auto ele : arr) {
    sum += ele;
  }
  if (sum % 2) {
    return false;
  }
  sum /= 2;

  int len = arr.size();
  vector<int> dp(sum + 1, 0);
  dp[0] = 1;
  for (int i = 1; i < len + 1; ++i) {
    for (int j = sum; j > 0; --j) {
      if (!dp[j] && j >= arr[i - 1]) {
        dp[j] = dp[j - arr[i - 1]];
      }
    }
  }
  return dp[sum];
}

int main() {
  vector<int> arr = {3, 4, 1};
  cout << canPartition1(arr) << endl;
  cout << canPartition2(arr) << endl;
  cout << canPartition3(arr) << endl;

  return 0;
}
